The problem Hamiltonian of the adiabatic quantum algorithm for themaximum-weight independent set problem (MIS) that is based on the reduction tothe Ising problem (as described in [Choi08]) has flexible parameters. We showthat by choosing the parameters appropriately in the problem Hamiltonian(without changing the problem to be solved) for MIS on CK graphs, we canprevent the first order quantum phase transition and significantly change theminimum spectral gap. We raise the basic question about what the appropriateformulation of adiabatic running time should be. We also describe adiabaticquantum algorithms for Exact Cover and 3SAT in which the problem Hamiltoniansare based on the reduction to MIS. We point out that the argument in Altshuleret al.(arXiv:0908.2782 [quant-ph]) that their adiabatic quantum algorithmfailed with high probability for randomly generated instances of Exact Coverdoes not carry over to this new algorithm.
展开▼
